"""
WA1 = 逻辑漏洞：没考虑到匹配到的字符可能已经是n了，相当于没有匹配到；导致如果是最后一个字符没有匹配到则会输出匹配到
"""

from collections import Counter
from itertools import chain
from itertools import permutations


class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        n = len(s)

        # ---------- 预处理字符串 ----------
        # 当前在第i个下标之前，下一个某字母的下标
        # 时空复杂度 : n * 26
        nxt_lst = [[n] * 26 for _ in range(n)]
        for i in range(n - 1, -1, -1):
            if i < n - 1:
                nxt_lst[i] = nxt_lst[i + 1].copy()
            nxt_lst[i][ord(s[i]) - 97] = i

        # 计算每个位置之后各个字母的数量
        num_lst = [[0] * 26 for _ in range(n)]
        for i in range(n - 1, -1, -1):
            if i < n - 1:
                num_lst[i] = num_lst[i + 1].copy()
            num_lst[i][ord(s[i]) - 97] += 1

        # ---------- 计算最优子序列 ----------
        # 计算子序列最大长度
        # max_length <= 7 : n < k * 8  -> k > n / 8 -> n // k
        max_length = n // k

        # 统计每个字母的出现频数
        count = Counter(s)

        # 计算子序列中每个字母的最大数量
        # 字母总数 <= 7
        per_count = {ch: num // k for ch, num in count.items() if num >= k}

        # 构造所有可能的顺序组合
        # 可能的子序列 < 7 * 7! = 7 * 5040
        maybe_lst = list(chain(*[[ch] * num for ch, num in per_count.items()]))

        # 从长到短遍历所有可能的子序列
        for length in range(len(maybe_lst), 0, -1):
            # 生成当前长度所有可能的子序列
            all_maybe = set(permutations(maybe_lst, length))
            all_maybe = sorted(all_maybe, reverse=True)
            # 遍历所有可能的子序列
            for maybe in all_maybe:
                # 计算需要的每个字母的数量
                need = Counter(maybe)
                need = {ch: num * k for ch, num in need.items()}
                need_num = length * k

                # 检查子序列是否符合
                i0 = 0
                j = 0
                while i0 < n and need_num > 0:
                    if need_num % k == 0:  # 每遍历一次子序列，检查一次剩余字符串是否还够遍历
                        for check in need:
                            if num_lst[i0][ord(check) - 97] < need[check]:
                                break

                    ch = maybe[j]
                    i1 = nxt_lst[i0][ord(ch) - 97]

                    if i1 < n:  # 判断是否成功找到对应字符
                        need[ch] -= 1
                        i0 = i1 + 1
                        j = (j + 1) % length
                        need_num -= 1
                    else:
                        break

                # 判断是否可以成功匹配子序列
                if need_num == 0:
                    return "".join(maybe)

        # 没有任何可以取到的子序列的情况的情况
        return ""


if __name__ == "__main__":
    print(Solution().longestSubsequenceRepeatedK(s="letsleetcode", k=2))  # "let"
    print(Solution().longestSubsequenceRepeatedK(s="bb", k=2))  # "b"
    print(Solution().longestSubsequenceRepeatedK(s="ab", k=2))  # ""
    print(Solution().longestSubsequenceRepeatedK(s="bbabbabbbbabaababab", k=3))  # "bbbb"

    # 测试用例294/311
    print(Solution().longestSubsequenceRepeatedK("lyzalyzalyjzzalyzalyzap", 5))
